{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Penalty for a Shop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: bestClosingTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #商店的最少代价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个顾客访问商店的日志，用一个下标从 <strong>0</strong>&nbsp;开始且只包含字符&nbsp;<code>'N'</code> 和&nbsp;<code>'Y'</code>&nbsp;的字符串&nbsp;<code>customers</code>&nbsp;表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果第&nbsp;<code>i</code>&nbsp;个字符是&nbsp;<code>'Y'</code>&nbsp;，它表示第&nbsp;<code>i</code>&nbsp;小时有顾客到达。</li>\n",
    "\t<li>如果第&nbsp;<code>i</code>&nbsp;个字符是&nbsp;<code>'N'</code>&nbsp;，它表示第 <code>i</code>&nbsp;小时没有顾客到达。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果商店在第&nbsp;<code>j</code>&nbsp;小时关门（<code>0 &lt;= j &lt;= n</code>），代价按如下方式计算：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在开门期间，如果某一个小时没有顾客到达，代价增加 <code>1</code>&nbsp;。</li>\n",
    "\t<li>在关门期间，如果某一个小时有顾客到达，代价增加&nbsp;<code>1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回在确保代价 <strong>最小</strong>&nbsp;的前提下，商店的&nbsp;<strong>最早</strong>&nbsp;关门时间。</p>\n",
    "\n",
    "<p>注意，商店在第 <code>j</code>&nbsp;小时关门表示在第 <code>j</code> 小时以及之后商店处于关门状态。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>customers = \"YYNY\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "- 第 0 小时关门，总共 1+1+0+1 = 3 代价。\n",
    "- 第 1 小时关门，总共 0+1+0+1 = 2 代价。\n",
    "- 第 2 小时关门，总共 0+0+0+1 = 1 代价。\n",
    "- 第 3 小时关门，总共 0+0+1+1 = 2 代价。\n",
    "- 第 4 小时关门，总共 0+0+1+0 = 1 代价。\n",
    "在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>customers = \"NNNNN\"\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>最优关门时间是 0 ，因为自始至终没有顾客到达。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>customers = \"YYYY\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>最优关门时间是 4 ，因为每一小时均有顾客到达。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= customers.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>customers</code>&nbsp;只包含字符&nbsp;<code>'Y'</code>&nbsp;和&nbsp;<code>'N'</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-penalty-for-a-shop](https://leetcode.cn/problems/minimum-penalty-for-a-shop/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-penalty-for-a-shop](https://leetcode.cn/problems/minimum-penalty-for-a-shop/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"YYNY\"', '\"NNNNN\"', '\"YYYY\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        minP = 0\n",
    "        ans = 0\n",
    "        curP = 0\n",
    "        for i in range(1, len(customers) + 1):\n",
    "            if customers[i - 1] == 'Y':\n",
    "                curP -= 1\n",
    "            else:\n",
    "                curP += 1\n",
    "            if curP < minP:\n",
    "                minP = curP\n",
    "                ans = i\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        c = Counter(customers)\n",
    "        res = cur = c[\"Y\"]\n",
    "        idx = -1\n",
    "        for i, v in enumerate(customers):\n",
    "            if v == \"Y\":\n",
    "                cur -= 1\n",
    "            else:\n",
    "                cur += 1\n",
    "            if cur < res:\n",
    "                res, idx = cur, i\n",
    "        return idx + 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        # 代价最小的情况下的最早关门时间\n",
    "        # costs = sum([1 for x in customers if x == 'Y'])\n",
    "        costs = customers.count('Y')\n",
    "        min_cost = costs\n",
    "        res = 0\n",
    "        for i,v in enumerate(customers):\n",
    "            if v == 'Y':\n",
    "                costs -= 1\n",
    "            else:\n",
    "                costs += 1\n",
    "            if costs < min_cost:\n",
    "                min_cost = costs\n",
    "                res = i + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        y = customers.count('Y')\n",
    "        cur_n = 0\n",
    "        min_ = 0\n",
    "        cost = len(customers)\n",
    "        for i in range(len(customers)+1):\n",
    "            print(cost,y-i+2*cur_n)\n",
    "            if cost > y-i+2*cur_n:\n",
    "                cost = y-i+2*cur_n\n",
    "                min_ = i\n",
    "            if i < len(customers) and customers[i] == 'N':\n",
    "                cur_n += 1\n",
    "        return min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        ans = 0\n",
    "        min_cost = cost = customers.count('Y')\n",
    "        for i, c in enumerate(customers, 1):\n",
    "            if c == 'N': cost += 1\n",
    "            else:\n",
    "                cost -= 1\n",
    "                if cost < min_cost:\n",
    "                    cost = min_cost\n",
    "                    ans = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(customers)\n",
    "        mx = n \n",
    "        cnty = 0\n",
    "        toty = customers.count('Y')\n",
    "        for i in range(n + 1):\n",
    "            cur = i - cnty + toty - cnty\n",
    "            if cur < mx:\n",
    "                mx = cur\n",
    "                ans = i \n",
    "            if i < n: cnty += int(customers[i] == 'Y')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        cn = 0; ans = 0\n",
    "        for i, c in enumerate(customers):\n",
    "            if cn == 0:\n",
    "                if c == 'Y':  ans = i + 1\n",
    "                else:        cn += 1\n",
    "            else:\n",
    "                if c == 'Y': cn -= 1\n",
    "                else:        cn += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        #首先应该计算Y和N的总数\n",
    "        #左侧的N和右侧的Y都会被记为代价\n",
    "        cur_cost=Counter(customers)[\"Y\"]\n",
    "        final=cur_cost\n",
    "        res=-1\n",
    "        for ind,cur in  enumerate(customers):\n",
    "            cur_cost+=-1 if(cur==\"Y\") else 1\n",
    "            if cur_cost<final:\n",
    "                final=cur_cost\n",
    "                res=ind\n",
    "            print(cur_cost)\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "\n",
    "        yy = sum([c == 'Y' for c in customers])\n",
    "\n",
    "        n = y = 0\n",
    "        ans = None\n",
    "        min_ = float('inf')\n",
    "\n",
    "        for i in range(len(customers) + 1):\n",
    "            val = yy - y + n\n",
    "\n",
    "            if val < min_:\n",
    "                min_ = val\n",
    "                ans = i \n",
    "            \n",
    "            if i == len(customers):\n",
    "                break\n",
    "\n",
    "            if customers[i] == 'Y':\n",
    "                y += 1\n",
    "            else:\n",
    "                n += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "\n",
    "        cus = [ 1 if i == 'Y' else 0 for i in customers]\n",
    "        \n",
    "        loss = sum(cus)\n",
    "        \n",
    "        waste = 0\n",
    "        \n",
    "        res = [0,loss]\n",
    "        \n",
    "        for idx,c in enumerate(cus,1):\n",
    "            \n",
    "            if c == 0:\n",
    "               waste += 1\n",
    "            else:\n",
    "               loss -= 1  \n",
    "            \n",
    "            r_temp = waste + loss\n",
    "           \n",
    "            if r_temp < res[1]:\n",
    "                res = [idx,r_temp]\n",
    "        \n",
    "        return res[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        t = 0 \n",
    "        n_before_t = 0\n",
    "        y_after_t = len(list(filter(lambda s: s == 'Y', customers)))\n",
    "        cost = n_before_t + y_after_t\n",
    "        min_cost = cost\n",
    "        best_t = t\n",
    "        for i in customers:\n",
    "            t +=1\n",
    "            if i == 'Y':\n",
    "                y_after_t -=1\n",
    "            else:\n",
    "                n_before_t +=1\n",
    "            cost = n_before_t + y_after_t\n",
    "            if min_cost > cost:\n",
    "                min_cost = cost\n",
    "                best_t = t \n",
    "        return best_t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        openlist = [0] * n\n",
    "        closelist = [0] * n \n",
    "        costlist = [0] * n\n",
    "        for i , c in enumerate(customers):\n",
    "            if c == 'Y':\n",
    "                closelist[i] = 1\n",
    "            else:\n",
    "                openlist[i] = 1\n",
    "        print(openlist)\n",
    "        print(closelist)\n",
    "\n",
    "        sumopen = sum(openlist)\n",
    "        sumclose = sum(closelist)\n",
    "        ans = 0\n",
    "        cost = sumclose\n",
    "        ope = clo = 0\n",
    "        for i in range(n):\n",
    "            ope += openlist[i]\n",
    "            clo += closelist[i] \n",
    "            tmp = ope + (sumclose - clo)\n",
    "            if tmp < cost:\n",
    "                cost = tmp\n",
    "                ans = i\n",
    "        if cost == sumclose: \n",
    "            return 0\n",
    "        return ans+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        presum = [0 for _ in range(n + 1)]\n",
    "        for i, c in enumerate(customers):\n",
    "            presum[i + 1] = presum[i] + (1 if c == 'Y' else -1)\n",
    "        \n",
    "        max_i = presum.index(max(presum))\n",
    "        return max_i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        s = [0]\n",
    "        for c in customers:\n",
    "            if c == 'Y':\n",
    "                s.append(s[-1] + 1)\n",
    "            else:\n",
    "                s.append(s[-1] - 1)\n",
    "        mx = max(s)\n",
    "        for i,x in enumerate(s):\n",
    "            if x == mx:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        # 两个数组，A 里边的元素代表i小时关门，因为之前开门无客的代价\n",
    "        # B数组代表i小时关门，因为之后关门有客的代价。\n",
    "        n = len(customers)\n",
    "        cost = [0 for i in range(n+1)]\n",
    "        \n",
    "        ans = n\n",
    "        oc = cc = 0\n",
    "        for i in range(1,n+1):\n",
    "            if customers[i-1] == \"N\":\n",
    "                oc += 1\n",
    "            cost[i] = oc\n",
    "        val = cost[n]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if customers[i] == \"Y\":\n",
    "                cc += 1\n",
    "            cost[i] += cc\n",
    "            if cost[i] <= val:\n",
    "                ans = i\n",
    "                val = cost[i]\n",
    "        #print(cost)     \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        pre = [0] * (n+1)\n",
    "        suf = [0] * (n+1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            suf[i] = suf[i+1]\n",
    "            if customers[i] == 'Y':\n",
    "                suf[i] += 1\n",
    "        ans = int(1e9)\n",
    "        max_cost = int(1e9)\n",
    "        pre_cost = 0\n",
    "        for i in range(n+1):\n",
    "            if pre_cost + suf[i] < max_cost:\n",
    "                max_cost = pre_cost + suf[i]\n",
    "                ans = i\n",
    "            if i < n and customers[i] == 'N':\n",
    "                pre_cost += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n=len(customers)\n",
    "        s=sum(1 for i in customers if i=='Y')\n",
    "        cost=[0]*(n+1)\n",
    "        cost[0]=s\n",
    "        t=0\n",
    "        mi=[s,0]\n",
    "        for i,c in enumerate(customers):\n",
    "            t+=1 if c=='N' else 0\n",
    "            cost[i+1]=t+s-(1+i-t)\n",
    "            if mi[0]>cost[i+1]:\n",
    "                mi=[cost[i+1],i+1]\n",
    "        #print(cost)\n",
    "        return mi[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n=len(customers)\n",
    "        s=customers.count(\"Y\")\n",
    "        t=customers.count(\"N\")\n",
    "        dp=[s]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if customers[i-1]==\"Y\":\n",
    "                dp[i]=dp[i-1]-2\n",
    "            else:\n",
    "                dp[i]=dp[i-1]+2\n",
    "        c=min(dp)\n",
    "        for j in range(n+1):\n",
    "            if dp[j]==c:\n",
    "                return j\n",
    "                break\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        #customers=\"YYYY\"\n",
    "        n  = len(customers)\n",
    "        front, back = [0]* (n + 1), [0]* (n + 1)\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if customers[i] == 'Y':\n",
    "                back[i] = back[i + 1] + 1\n",
    "            else:\n",
    "                back[i] = back[i + 1] - 1\n",
    "        #print(back)\n",
    "        res, tar = 0, float('inf')\n",
    "        for i in range(n+1):\n",
    "            if tar > back[i]:\n",
    "                res = i\n",
    "                tar = back[i]\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, c: str) -> int:\n",
    "        n = len(c)\n",
    "        pref = [0]\n",
    "        for ci in c:\n",
    "            tmp = 1 if ci == \"Y\" else 0\n",
    "            pref.append(pref[-1] + tmp)\n",
    "        \n",
    "        ans = inf\n",
    "        idx = inf\n",
    "        cnt = 0\n",
    "        # print(pref)\n",
    "        for i in range(n, -1, -1):\n",
    "            if i < n and c[i] == \"Y\":\n",
    "                cnt += 1\n",
    "            if ans >= cnt + (i - pref[i]):\n",
    "                ans = cnt + (i - pref[i])\n",
    "                idx = i\n",
    "        return idx\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        n_open = [0] * n\n",
    "        for i in range(n):\n",
    "            if customers[i] == 'Y':\n",
    "                if i==0:\n",
    "                    n_open[i]=1\n",
    "                else:\n",
    "                    n_open[i] = n_open[i-1]+1\n",
    "            else:\n",
    "                if i > 0:\n",
    "                    n_open[i] = n_open[i-1]\n",
    "        \n",
    "        time_close = 0\n",
    "        cost = n+1\n",
    "        print(n_open)\n",
    "        for i in range(n):\n",
    "            tmp = 0\n",
    "            if customers[i] == 'Y':\n",
    "                tmp += n_open[-1]-n_open[i] + 1\n",
    "                tmp += (i-(n_open[i]-1))\n",
    "            else:\n",
    "                tmp += n_open[-1]-n_open[i]\n",
    "                tmp += (i-n_open[i])\n",
    "            if tmp<cost:\n",
    "                time_close = i\n",
    "                cost = tmp\n",
    "        print(cost, n-n_open[-1])\n",
    "        if n-n_open[-1]<cost:\n",
    "            time_close = n\n",
    "        return time_close\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        # 思路: 算出每一个点前面的代价(不含),和后面的代价(含)\n",
    "        n = len(customers)\n",
    "        pre = [0 for i in range(n + 1)]\n",
    "        pos = [0 for i in range(n + 1)]\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i - 1]\n",
    "            if customers[i-1] == 'N':\n",
    "                pre[i] += 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            pos[i] = pos[i + 1]\n",
    "            if customers[i] == 'Y':\n",
    "                pos[i] += 1\n",
    "        res, idx = float('inf'), 0\n",
    "        for i in range(0, n+1):\n",
    "            if pre[i] + pos[i] < res:\n",
    "                idx = i\n",
    "                res = pre[i] + pos[i]\n",
    "        return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        left,right = [],[]\n",
    "        n = len(customers)\n",
    "        price = 0\n",
    "        for i,x in enumerate(customers):\n",
    "            left.append(price)\n",
    "            if x == 'N':\n",
    "                price += 1\n",
    "        price = 0\n",
    "        for i,x in enumerate(reversed(customers)):\n",
    "            if x == 'Y':\n",
    "                price += 1\n",
    "            right.append(price)\n",
    "        right.reverse()\n",
    "        res = 0\n",
    "        price = n\n",
    "        for i in range(n):\n",
    "            if left[i]+right[i] < price:\n",
    "                price = left[i]+right[i]\n",
    "                res = i\n",
    "        if left[n-1] < price:\n",
    "            res = n\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        len_sum = len(customers)\n",
    "        pre_sumn = [0] * (len_sum + 1)\n",
    "        pre_cntn = 0\n",
    "        for i in range(len_sum + 1):\n",
    "            pre_sumn[i] = pre_cntn\n",
    "            if 0 <= i and i < len_sum and customers[i] == 'N':\n",
    "                pre_cntn += 1\n",
    "\n",
    "        suf_sumy = [0] * (len_sum + 1)\n",
    "        suf_cnty = 0\n",
    "        for i in range(len_sum, -1, -1):\n",
    "            if 0 <= i and i < len_sum and customers[i] == 'Y':\n",
    "                suf_cnty += 1\n",
    "            suf_sumy[i] = suf_cnty\n",
    "\n",
    "        print(pre_sumn)\n",
    "        print(suf_sumy)\n",
    "\n",
    "        min_time = len_sum + 1\n",
    "        min_cost = sys.maxsize\n",
    "\n",
    "        for i in range(len_sum + 1):\n",
    "            cost = pre_sumn[i] + suf_sumy[i]\n",
    "            if cost < min_cost:\n",
    "                min_cost = cost\n",
    "                min_time = i\n",
    "\n",
    "        return min_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        preN = [0] * len(customers)\n",
    "        afterY = [0] * len(customers)\n",
    "\n",
    "        cur = 0\n",
    "        for i in range(len(customers)):\n",
    "            if(customers[i] == 'N'):\n",
    "                cur = cur + 1\n",
    "            preN[i] = cur\n",
    "        \n",
    "        cur = 0\n",
    "        for i in range(len(customers) -1, -1,-1):\n",
    "            if( customers[i] == 'Y'):\n",
    "                cur = cur + 1\n",
    "            afterY[i] = cur\n",
    "        \n",
    "        print(preN)\n",
    "        print(afterY)\n",
    "\n",
    "        curSum = afterY[0]\n",
    "        curIndex = 0\n",
    "        for i in range(len(customers) + 1):\n",
    "            if(i == 0):\n",
    "                preValue = 0\n",
    "            else:\n",
    "                preValue = preN[i-1]\n",
    "\n",
    "            if( i == len(customers) ):\n",
    "                afterValue = 0\n",
    "            else:\n",
    "                afterValue = afterY[i]\n",
    "            \n",
    "            if( afterValue + preValue < curSum):\n",
    "                curSum = afterValue + preValue\n",
    "                curIndex = i\n",
    "        return curIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        l = [0] * (n + 1) # 第i个位置前有多少N\n",
    "        r = [0] * (n + 1) # 第i个位置及后有多少Y\n",
    "        for i in range(1, n + 1):\n",
    "            l[i] = l[i - 1] + (1 if customers[i - 1] == 'N' else 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            r[i] = r[i + 1] + (1 if customers[i] == 'Y' else 0)\n",
    "        \n",
    "        res, minn = 0, inf\n",
    "        for i in range(n + 1):\n",
    "            if l[i] + r[i] < minn: \n",
    "                minn = l[i] + r[i];\n",
    "                res = i;\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        l = [0] * (n + 1) # 第i个位置前有多少N\n",
    "        r = [0] * (n + 1) # 第i个位置及后有多少Y\n",
    "        for i in range(1, n + 1):\n",
    "            l[i] = l[i - 1] + (1 if customers[i - 1] == 'N' else 0)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            r[i] = r[i + 1] + (1 if customers[i] == 'Y' else 0)\n",
    "        \n",
    "        res, minn = 0, inf\n",
    "        for i in range(n + 1):\n",
    "            if l[i] + r[i] < minn: \n",
    "                minn = l[i] + r[i];\n",
    "                res = i;\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, c: str) -> int:\n",
    "        n = len(c)\n",
    "        pn = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            pn[i] = pn[i - 1] + (c[i] == 'N')\n",
    "        sy = [0 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            sy[i] = sy[(i + 1) % n] + (c[i] == 'Y')\n",
    "        \n",
    "        res = c.count('Y')\n",
    "        time = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            cost = pn[i - 1] + sy[i]\n",
    "            if cost < res:\n",
    "                res =  cost\n",
    "                time = i\n",
    "        \n",
    "        cost = c.count('N')\n",
    "        if cost < res:\n",
    "            res = cost\n",
    "            time = n\n",
    "        \n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "\n",
    "        prey, sufy = [0]*(n+1), [0]*(n+1)\n",
    "        for i in range(n+1):\n",
    "            if i == 0: continue\n",
    "            prey[i] = prey[i-1]+(customers[i-1]==\"Y\")\n",
    "\n",
    "        for i in range(n,-1,-1):\n",
    "            if i == n: continue\n",
    "            sufy[i] = sufy[i+1]+(customers[i]==\"Y\") if i != n-1 else customers[i]==\"Y\"\n",
    "\n",
    "        min_cost = None\n",
    "        ans = None\n",
    "        for i in range(n+1):\n",
    "            t = i+1-prey[i]+sufy[i]\n",
    "            if min_cost is None or t < min_cost:\n",
    "                min_cost = t\n",
    "                ans = i\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        pre=[0]*(len(customers)+1)\n",
    "        for i in range(len(customers)):\n",
    "            pre[i+1]=pre[i]+(customers[i]=='N')\n",
    "        suf=[0]*(len(customers)+1)\n",
    "        for i in range(len(customers)-1,-1,-1):\n",
    "            suf[i]=suf[i+1]+(customers[i]=='Y')\n",
    "        res=0\n",
    "        for i in range(len(pre)):\n",
    "            if pre[i]+suf[i]<pre[res]+suf[res]:\n",
    "                res=i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        Y=[0]*(len(customers)+1)\n",
    "        N=[0]*(len(customers)+1)\n",
    "        s=0\n",
    "        for i in range(len(customers)-1,-1,-1):\n",
    "            if customers[i]=='Y':\n",
    "                s+=1\n",
    "            Y[i]=s\n",
    "        s=0\n",
    "        for j in range(1,len(customers)+1):\n",
    "            if customers[j-1]=='N':\n",
    "                s+=1\n",
    "            N[j]=s\n",
    "        dp=[Y[i]+N[i] for i in range(len(customers)+1)]\n",
    "\n",
    "        num=10**5+1\n",
    "        res=0\n",
    "        for i in range(len(customers)+1):\n",
    "            if dp[i]<num:\n",
    "                num=dp[i]\n",
    "                res=i\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestClosingTime(self, customers: str) -> int:\n",
    "        n = len(customers)\n",
    "        suf1 = [0] * n\n",
    "        suf2 = [0] * n\n",
    "        if customers[-1] == 'Y':\n",
    "            suf1[-1] = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if customers[i] == 'Y':\n",
    "                suf1[i] = suf1[i + 1] + 1\n",
    "            else:\n",
    "                suf1[i] += suf1[i + 1]\n",
    "        for i in range(1, n):\n",
    "            if customers[i - 1] == 'N':\n",
    "                suf2[i] += suf2[i - 1] + 1\n",
    "            else:\n",
    "                suf2[i] += suf2[i - 1]\n",
    "        x1= customers.count('N')\n",
    "        suf2.append(x1)\n",
    "        suf1.append(0)\n",
    "        res = 1e9\n",
    "        k = -1\n",
    "        for i in range(n + 1):\n",
    "            x = suf1[i] + suf2[i]\n",
    "            if x < res:\n",
    "                res = x\n",
    "                k = i\n",
    "        return k"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
